// @algorithm @lc id=60 lang=cpp 
// @title permutation-sequence


// @test(3,3)="213"
// @test(4,9)="2314"
// @test(3,1)="123"
class Solution {
public:
    string getPermutation(int n, int k) {
        string nstr(n, '1');
        for(int i=1; i<n; i++)
            nstr[i] = '1'+i;
        for(int i=1; i<k; i++)
            next_permutation(nstr.begin(), nstr.end());
        return nstr;
    }
};